package com.zpself.module.算法练习.算法.动态规划;

import java.util.HashSet;
import java.util.Set;

/**
 * //两字符串，求他们最长公共子序列，可不连续，但顺序要对得上，  比如  acd   accccd  公共  acd
 * @author By ZengPeng
 * @Description
 * @date in  2020/10/9 16:51
 * @Modified By
 */
public class 最大公共子序列 {
   static Set<String> result = new HashSet<>();
    public static void main(String[] args) {
        System.out.println("最长公共子序列为:"+getPublicString("BDCABA","ABCBDAB"));
        //System.out.println(LCS("acd","accccd",0,0));
    }


    //动态分布
    private static String getPublicString(String strA, String strB){
        char[] A = strA.toCharArray();
        char[] B = strB.toCharArray();
        int[][] dp = new int[A.length+1][B.length+1];
        //dp
        for(int i = 0; i < A.length+1; i++){
            for(int j = 0; j < B.length+1; j++){
                if (i == 0 || j == 0){
                    dp[i][j] = 0;
                    continue;
                }
                if (A[i-1] ==  B[j-1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] =Math.max(dp[i - 1][j ],dp[i ][j - 1]);
                }
            }

        }
       //打印表格
        for(int i = 0; i < A.length+1; i++){
            for(int j = 0; j < B.length+1; j++){
                System.out.print(dp[i][j]);
            }
            System.out.println();
        }
        printAllLCS(A,B,A.length,B.length,dp,"");
        return result.toString();
    }

    private static void printAllLCS(char[] str1, char[] str2, int i, int j,
                                    int[][] veca, String lcs_str) {
        //注意这里形参lcs_str不可以为引用，这里需要每次调用lcs_str都重新生成一个对象
        StringBuilder lcs_strBuilder = new StringBuilder(lcs_str);
        while (i > 0 && j > 0) {
            if (str1[i - 1] == str2[j - 1]) {
                lcs_strBuilder.insert(0, str1[i - 1]); //逆向存放
                --i;
                --j;
            } else {
                if (veca[i - 1][j] > veca[i][j - 1]) //向左走
                    --i;
                else if (veca[i - 1][j] < veca[i][j - 1]) //向上走
                    --j;
                else { //此时向上向右均为LCS的元素
                    printAllLCS(str1, str2, i - 1, j, veca, lcs_strBuilder.toString());
                    printAllLCS(str1, str2, i, j - 1, veca, lcs_strBuilder.toString());
                    return;
                }
            }
        }
        lcs_str = lcs_strBuilder.toString();
        result.add(lcs_str);
    }

    //递归实现-- (n * 2的m次方)
    private static int LCS(String s1, String s2, int i, int j){
        if(i>=s1.length()||j>=s2.length())
            return 0;
        if(s1.charAt(i)==s2.charAt(j))
            return LCS(s1,s2,i+1,j+1)+1;
        else
            return LCS(s1,s2,i+1,j)>LCS(s1,s2,i,j+1) ? LCS(s1,s2,i+1,j):LCS(s1,s2,i,j+1);
    }

}
